package 我的Java学习_算法基础.day_07;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author 挚爱之夕
 * @date 2021/8/20 - 08 - 20 - 15:17
 * @Description: 我的暑假Java学习.day_07
 * @Version: 1.0
 */
public class _112_全排列_中 {
    static ArrayList<String> res = new ArrayList<>();
    public static void main(String[] args) {
        String s ="bca";
        ArrayList<String> list=getPermutation(s);
        System.out.println(list);
    }

    /**
     * 回溯法
     * @param s 原串
     * @return s的全排列
     */
    public static ArrayList<String> getPermutation(String s){
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        getPermutation(arr,0);
        return res;
    }
    private static void getPermutation(char[] arr,int k){
        if(k==arr.length){//排好了一种情况
            res.add(new String(arr));
        }
        //从k位开始的每个字符，都尝试放在新排列的k这个位置
        for(int i = k;i<arr.length;i++){
            swap(arr,k,i);//把后面每个字符换到k位
            getPermutation(arr,k+1);
            swap(arr,k,i);//回溯
        }
    }
    static void swap(char[] arr,int i,int j){
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
